

package proyectodatos1verano.modelo;


public class Lista implements ILista {
    private Comparable vector[];
    private static int tammano;
    private int tamObjetos;
  
    
    public Lista(){
        tammano=250000;
        tamObjetos=0;
      
        vector= new Comparable[tammano];
    }

    @Override
    public int size() {
        return tamObjetos;
    }

    @Override
    public boolean isEmpty() {
        if(vector[0]==null)
            return true;
        else
            return false;
    }

    @Override
    public boolean contains(Comparable o) {
        
        return BSearch(o)>-1;
    }

    

    @Override
    public boolean add(Comparable e) {
        if(tamObjetos<tammano){
            
            vector[tamObjetos]=e;
            tamObjetos++;
            return true;
        }else{
            
           
            int porcentaje= tammano*50/100;
            ensureCapacity(porcentaje);
            vector[tamObjetos]=e;
            tamObjetos++;
            return true;
        }
        
    }

    @Override
    public boolean remove(Comparable o) {
        Comparable nuevo[]=new Comparable[tammano];
        boolean busqueda=false;
        for (int i = 0; i < tamObjetos; i++) {
            if(o.equals(vector[i])){
                vector[i]=null;
                nuevo[i]=vector[i+1];
                busqueda=true;
            }else if(busqueda){
                nuevo[i]=vector[i+1];
            }else{
                nuevo[i]= vector[i];
            }
        }if(busqueda){
            vector=nuevo;
            tamObjetos--;
            return true;
        }return false;
    }

    @Override
    public boolean containsAll(ILista clctn) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

    @Override
    public boolean addAll(ILista clctn) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

    @Override
    public boolean removeAll(ILista clctn) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

    @Override
    public boolean retainAll(ILista clctn) {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

    @Override
    public void clear() {
        
        for(int i=0; i<tammano; i++){
            vector[i]=null;
            
        }
        tamObjetos=0;
    }
    
    @Override
    public void ensureCapacity(int i){
        int tamNuevo=tammano+i;
        Comparable[] nuevo = new Comparable[tamNuevo]; 
	for(int r = 0; r<tammano-1; r++){
	    nuevo[r] = vector[r];
	}
        tammano=tamNuevo;
        System.out.println(vector.length);
        vector = nuevo;
    }
    @Override
    public void sort(){
       // System.out.println(tammano);
        quickSort(vector, 0,tamObjetos-1);
    }
    public void quickSort(Comparable[] a,int left, int right){
        if(left<right){
            int p= partition(a, left, right);
            quickSort(a, left, p-1);
            quickSort(a, p+1, right);
        }
        
        
    }
    
    private static int partition(Comparable[] a, int left, int right){
        Comparable pivot= a[left];
        int p=left;
        
        for (int r = left+1 ; r <= right; r++) {
            
            
            int comp=a[r].compareTo(pivot);
            if(comp<0){
                a[p]=a[r];  
                a[r]=a[p+1];
                a[p+1]=pivot;
                p++;
            }
        }
        return p;
    }
    
    @Override
    public ILista clone(){
        Lista nueva=new Lista();
        for (int r = 0; r < tamObjetos; r++) {
            nueva.add(vector[r]);
        }
        return nueva;
    }

    @Override
    public boolean add(int pos, Comparable obj) {
        if(pos<=tamObjetos+1){
            if(pos==tamObjetos||tamObjetos==0){
                vector[pos]=obj;
                tamObjetos++;
            }else{
                Comparable[] nVector= new Comparable[tammano];
                for (int i = 0; i < tamObjetos; i++) {
                    if(pos==i){
                        nVector[i]=obj;
                        nVector[i+1]=vector[i];
                    }else if(pos<i){
                        nVector[i+1]=vector[i];
                    }else{
                        nVector[i]=vector[i];
                    }
                }
                vector=nVector;
                tamObjetos++;
                return true;
            }
        }
        return false;
    }

    @Override
    public Comparable get(int pos) {
        return vector[pos];
    }

    @Override
    public boolean remove(int pos) {
        if(pos<tamObjetos){
            Comparable[] nvector= new Comparable[tammano];
            for (int i = 0; i < tamObjetos; i++) {
                if(i<pos){
                    nvector[i]=vector[i];
                }else if(i>pos){
                    nvector[i-1]=vector[i];
                }
            }
            tamObjetos--;
            vector=nvector;
            return true;
        }
        
        return false;
    }
    
    public void imprimirUltimo(){
        System.out.println(vector[tamObjetos-1].toString());
    }
    
    public void imprimir(){
        for (int i = 0; i < tamObjetos; i++) {
            System.out.println(vector[i]);
        }
    }

    @Override
    public int BSearch(Comparable target) {
        
        return BS(target, vector, 0, tamObjetos);
    }
    
    private int BS(Comparable target, Comparable[] a, int left, int right) {
        if(!isEmpty()){
            int l = left, r = right;
            while (l <= r) {
                int x=l+r;

                int m = x / 2 ;
                //System.out.println(m);
                int comp = target.compareTo (a [m]);
                
                if (comp == 0)
                    return m;
                else if (comp < 0){

                    r = m - 1 ;

                }else{ // comp > 0
                    l= m + 1 ;
                }
            }
        }
        return -1;
    }
    
    public Lista devuelveIndices(){
        Lista l1= new Lista();
        for (int i = 0; i < tamObjetos; i++) {
            String a= (String) vector[i];
            if(a.length()>=5){
                l1.add(a.substring(0, 5));
            }else if(a.length()<5){
                l1.add(a);
            }
        }
        return l1;
    }
    
    
    
}
